#
# @lc app=leetcode.cn id=10 lang=python3
#
# [10] 正则表达式匹配
#


# @lc code=start
# 解法1：根据第一个位置情况分类
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        """
        根据第一个位置情况分类
        """

        if not (bool(s) | bool(p)):
            return True
        if s and not p:
            return False
        if not s and p:
            if len(p) > 1 and p[1] == '*':
                return self.isMatch(s, p[2:])
            return False

        if p[0] == s[0]:
            if len(p) > 1 and p[1] == '*':
                if len(p) > 2:
                    i = 0
                    l = len(s)
                    while i < l:
                        if self.isMatch(s[i:], p[2:]):
                            return True
                        if s[i] != p[0]:
                            return False
                        i += 1
                    if len(p) % 2 == 1 or not all(map(lambda x: x == '*', p[1::2])):
                        return False
                for i in s:
                    if i != p[0]:
                        return False
                return True
            return self.isMatch(s[1:], p[1:])

        if p[0] == '.':
            if len(p) > 1 and p[1] == '*':
                if len(p) > 2:
                    i = 0
                    l = len(s)
                    while i < l:
                        if self.isMatch(s[i:], p[2:]):
                            return True
                        i += 1
                    if len(p) % 2 == 0 and all(map(lambda x: x == '*', p[1::2])):
                        return True
                    return False
                return True
            return self.isMatch(s[1:], p[1:])

        if len(p) > 1 and p[1] == '*':
            return self.isMatch(s, p[2:])
        return False

    def isMatch2(self, s: str, p: str) -> bool:
        """
        根据第二个位置情况分类
        """

        if not p:
            return not bool(s)
        if not s:
            return len(p) % 2 == 0 and all([i == '*' for i in p[1::2]])

        firstMatch = p[0] == s[0] or p[0] == '.'

        if len(p) > 1 and p[1] == '*':
            return self.isMatch(s, p[2:]) or firstMatch and self.isMatch(s[1:], p)
        if firstMatch:
            return self.isMatch(s[1:], p[1:])
        return False

    def isMatch3(self, s: str, p: str) -> bool:
        """
        带memo 自顶而下
        """

        memo = {}

        def match(i, j):
            if (i, j) in memo:
                return memo[i, j]

            if j == len(p):
                memo[i, j] = i == len(s)
                return memo[i, j]
            firstMatch = i < len(s) and (p[j] == '.' or p[j] == s[i])
            if j + 1 < len(p) and p[j + 1] == '*':
                memo[i, j] = match(i, j + 2) or firstMatch and match(i + 1, j)
                return memo[i, j]
            memo[i, j] = firstMatch and match(i + 1, j + 1)
            return memo[i, j]

        return match(0, 0)

    def isMatch4(self, s: str, p: str) -> bool:
        """
        带memo 自底而上
        """

        sLen = len(s)
        pLen = len(p)
        memo = {(sLen, pLen): True}
        for i in range(sLen):
            memo[i, pLen] = False

        for i in range(len(s), -1, -1):
            for j in range(len(p) - 1, -1, -1):
                firstMatch = i < len(s) and (p[j] == '.' or s[i] == p[j])
                if j + 1 < len(p) and p[j + 1] == '*':
                    memo[i, j] = memo[i, j + 2] or firstMatch and memo[i + 1, j]
                elif firstMatch:
                    memo[i, j] = memo[i + 1, j + 1]
                else:
                    memo[i, j] = False
        return memo[0, 0]


if __name__ == '__main__':
    s = Solution()
    isMatch = s.isMatch

    print(isMatch("aa", "a") == False)
    print(isMatch("aa", "a*") == True)
    print(isMatch("ab", ".*") == True)
    print(isMatch("fghijkae", ".*ae") == True)
    print(isMatch("aab", "c*a*b") == True)
    print(isMatch("mississippi", "mis*is*p*.") == False)
    print(isMatch("aaa", "a*a") == True)
    print(isMatch("aaa", "ab*a*c*a") == True)
    print(isMatch("abbabaaaaaaacaa", "a*.*b.a.*c*b*a*c*") == True)
    print(isMatch("bcbabcaacacbcabac", "a*c*a*b*.*aa*c*a*a*") == True)
# @lc code=end
